/**
 * 两个链表a，b
 * 判断b释放为a的子序列
 * 
 * 思想，不断的比较，如果遇到不正确的，那么就回退，从b的开头重新比较
 * 链表不支持随机访问，所以不可以kmp优化
 */


#include"LinkedList.h"
int pattern(LinkedList *a,LinkedList *b){
    LinkedList *p=a;
    LinkedList*pre=p;//pre用来回退，记录每次比较的时候的开始节点
    LinkedList *q=b;
    while (p&&q)
    {
        if(p->val==q->val){
            p=p->next;
            q=q->next;
        }else{//如果不相等，就要从b的开头重新比较
            pre=pre->next;
            p=pre;
            q=b;
        }
    }
    //退出while之后，如果q为空，那么说明b是子序列
    //也就是b序列比较到最后了
    if(q==nullptr){
        return 1;
    }else{
        return 0;
    }
    
}